package leetcode_day._2021._202112._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/10 14:37
 * 给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出并返回 words 中的 最短补全词 。
 * 补全词 是一个包含 licensePlate 中所有的字母的单词。在所有补全词中，最短的那个就是 最短补全词 。
 * 在匹配 licensePlate 中的字母时：
 * 忽略 licensePlate 中的 数字和空格 。
 * 不区分大小写。
 * 如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
 * 算法：模拟
 */
public class _10_748 {
    public static void main(String[] args) {
        String s = new _10_748().shortestCompletingWord("1s3 PSt", new String[]{"step", "steps", "stripe", "stepple"});
        System.out.println(s);
    }

    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] nums = new int[26];
        int cnt = 0;
        for (int i = 0; i < licensePlate.length(); i++) {
            char c = licensePlate.charAt(i);
            if ((c >= '0' && c <= '9') || c == ' ') continue;
            c = Character.toLowerCase(c);
            ++nums[c - 'a'];
            ++cnt;
        }
        String ans = null;
        for (String word : words) {
            if (word.length() < cnt) continue;
            int[] tmp = new int[26];
            for (int i = 0; i < word.length(); i++) ++tmp[word.charAt(i) - 'a'];
            boolean flag = true;
            for (int i = 0; i < 26; i++)
                if (tmp[i] < nums[i]) {
                    flag = false;
                    break;
                }
            if (flag) ans = ans == null || ans.length() > word.length() ? word : ans;
        }
        return ans;
    }

}
